from tools_algorithm import *


class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
        if multiplier == 1:
            return nums
        q = []
        mx = 0
        for i, v in enumerate(nums):
            heappush(q, (v, i))
            mx = max(mx, v)
        while k > 0 and q[0][0] != mx:
            heapreplace(q, (q[0][0] * multiplier, q[0][1]))
            k -= 1
        d, m = divmod(k, len(nums))
        while m > 0:
            heapreplace(q, (q[0][0] * multiplier, q[0][1]))
            m -= 1
        ans = [0] * len(nums)
        mul = pow(multiplier, d, 1000000007)
        for v, i in q:
            ans[i] = v * mul % 1000000007
        return ans
